class Solution {
public:
    long long maxPower(vector<int>& stations, int r, int k) {
        int n = stations.size();
        vector<long long> sump(n + 1);
        for (int i = 0; i < n; i++) {
            int left = max(0, i - r), right = min(n, i + r + 1);
            sump[left] += stations[i], sump[right] -= stations[i];
        }

        // vector<int> power(n);
        // power[0] = sum[0];
        long long minpower = sump[0], cur = sump[0];
        for (int i = 1; i < n; i++) {
            // power[i] = power[i - 1] + sum[i];
            cur = cur + sump[i];
            minpower = min(cur, minpower);
        }

        //for(int s : sump) cout << s << " ";

        long long pl = minpower, pr = minpower + k;
        while (pl < pr) {
            long long pmid = (pl + pr) / 2 + 1;
            vector<long long> tmpsum(n + 1);
            tmpsum = sump;
            cur = 0;
            int diffk = k;
            bool b = true;
            for (int i = 0; i < n; i++) {
                cur = cur + tmpsum[i];
                if (cur < pmid) {
                    long long di = pmid - cur;
                    diffk -= di;
                    if (diffk < 0) {
                        b = false;
                        break;
                    }
                    tmpsum[min(n, i + 2 * r + 1)] -= di;
                    tmpsum[i] += di;
                    cur += di;
                }
            }
            if (b) pl = pmid;
            else pr = pmid - 1;
        }
        return pl;
    }
};